{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Chinese Whispers for Python"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This is an implementation of the [Chinese Whispers](https://doi.org/10.3115/1654758.1654774) graph clustering algorithm in Python.\n",
    "\n",
    "* <https://pypi.org/project/chinese-whispers/>\n",
    "* <https://chinese-whispers.readthedocs.io/>\n",
    "* <https://github.com/nlpub/chinese-whispers>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Version Information"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from chinese_whispers import __version__ as cw_version\n",
    "from networkx import __version__ as nx_version\n",
    "from matplotlib import __version__ as plt_version\n",
    "print('Chinese Whispers {}'.format(cw_version))\n",
    "print('NetworkX {}'.format(nx_version))\n",
    "print('matplotlib {}'.format(plt_version))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Clustering"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import networkx as nx\n",
    "from chinese_whispers import chinese_whispers, aggregate_clusters"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": false
   },
   "outputs": [],
   "source": [
    "G = nx.karate_club_graph()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Perform clustering of G, parameters weighting and seed can be omitted\n",
    "chinese_whispers(G, weighting='top', seed=1337) \n",
    "\n",
    "# Print the clusters in the descending order of size\n",
    "print('ID\\tCluster\\n')\n",
    "\n",
    "for label, cluster in sorted(aggregate_clusters(G).items(), key=lambda e: len(e[1]), reverse=True):\n",
    "    print('{}\\t{}\\n'.format(label, cluster))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Visualization"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%config InlineBackend.figure_formats = ['svg']\n",
    "\n",
    "import matplotlib.pyplot as plt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "colors = [1. / G.nodes[node]['label'] for node in G.nodes()]\n",
    "\n",
    "nx.draw_networkx(G, cmap=plt.get_cmap('jet'), node_color=colors, font_color='white')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Citation\n",
    "\n",
    "* [Ustalov, D.](https://github.com/dustalov), [Panchenko, A.](https://github.com/alexanderpanchenko), [Biemann, C.](https://www.inf.uni-hamburg.de/en/inst/ab/lt/people/chris-biemann.html), [Ponzetto, S.P.](https://www.uni-mannheim.de/dws/people/professors/prof-dr-simone-paolo-ponzetto/): [Watset: Local-Global Graph Clustering with Applications in Sense and Frame Induction](https://doi.org/10.1162/COLI_a_00354). Computational Linguistics 45(3), 423&ndash;479 (2019)\n",
    "\n",
    "```bibtex\n",
    "@article{Ustalov:19:cl,\n",
    "  author    = {Ustalov, Dmitry and Panchenko, Alexander and Biemann, Chris and Ponzetto, Simone Paolo},\n",
    "  title     = {{Watset: Local-Global Graph Clustering with Applications in Sense and Frame Induction}},\n",
    "  journal   = {Computational Linguistics},\n",
    "  year      = {2019},\n",
    "  volume    = {45},\n",
    "  number    = {3},\n",
    "  pages     = {423--479},\n",
    "  doi       = {10.1162/COLI_a_00354},\n",
    "  publisher = {MIT Press},\n",
    "  issn      = {0891-2017},\n",
    "  language  = {english},\n",
    "}\n",
    "```\n",
    "\n",
    "In case you require higher performance, please consider our Java implementation that also includes other graph clustering algorithms: <https://github.com/nlpub/watset-java>."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.6"
  },
  "title": "Chinese Whispers for Python"
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
